package com.cyc.basic.msb;

/**
 * @Description: 冒泡排序, 本质上就是利用两两比较
 * 时间复杂度为o(n^2), 空间复杂度为o(1), 稳定性为: 稳定, 因为冒泡排序采用的是两两比较, 如果两个值相同, 是不会交换位置的
 * @version 1.0
 * @author cyc
 * @date 2021/10/7 21:57
 */
public class DoubleSort {
    public static void main(String[] args) {
//        int[] arr = {5, 3, 6, 8, 1, 7, 9, 4, 2};
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};

        sort2(arr);
        print(arr);
    }

    static void sort(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--)
            //每次需要两两比对的数量
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
    }

    /**
     * 优化冒泡排序, 将其最好时间复杂度优化为o(n)
     * 优化外层循环
     * @param arr
     */
    static void sort2(int[] arr) {
        int num = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            int flag = 0;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = 1;
                }
                num++;
            }
            if (flag == 0) {
                //如果flag =0, 说明没有发生交换,也就是这是个排好序的数组, 这里直接return
                break;
            }
        }
        System.out.println("一共循环了" + num + "次");
    }


    static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    static void print(int[] arr) {
        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k]);
        }
        System.out.println();
    }
}
